package targetToOffer.forthDay;

/**
 * @author Godc
 * @description
 */
public class IsSubStructure {
}
class IsSubStructureSolution {
    /**
     * 时间复杂度最差o(M*N)，每个A节点都要和B比对
     * 双重DFS，isSubStructure层遍历A树的每一个节点去匹配B
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null)
            return false;
        // 确认当前节点和以A，B为根节点是否有相似结构
        if((A.val==B.val)&&check(A,B))
            return true;
        // 然后查看左右子树
        return isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }

    /**
     * check层判断以A，B为根节点有无出现子结构的情况
     * @param A
     * @param B
     * @return
     */
    public boolean check(TreeNode A,TreeNode B){
        // 说明B遍历完了，已经越过了叶子节点，说明有子结构
        if(B==null) return true;
        // 如果A遍历完了，但B没遍历完，或者A，B的值不相同，则说明不相同
        if(A==null||A.val!=B.val) return false;
        return check(A.left,B.left)&&check(A.right,B.right);
    }
}